import java.util.*;

public class SolutionInterview17_7 {

    static class Bing{
        int[] b;
        int[] size;

        public Bing(int n, int[] size){
            b=new int[n];
            for (int i=0;i<n;i++){
                b[i]=i;
            }
            this.size=size;
        }

        public void union(int x,int y){
            int xx=find(x);
            int yy=find(y);
            if (xx!=yy){
                b[xx]=yy;
                size[yy]+=size[xx];
            }
        }

        public int find(int x){
            return b[x]==x?x:(b[x]=find(b[x]));
        }
    }

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        Set<String> all=new HashSet<>();
        for (String synonym : synonyms) {
            String name1=synonym.substring(1,synonym.indexOf(','));
            String name2=synonym.substring(synonym.indexOf(',')+1,synonym.indexOf(')'));
            all.add(name1);
            all.add(name2);
        }
        for (String name : names) {
            all.add(name.substring(0,name.indexOf('(')));
        }
        int count=0;
        Map<String,Integer> map=new HashMap<>();
        Map<Integer,String> n=new HashMap<>();
        for (String s : all) {
            map.put(s,count);
            n.put(count,s);
            count++;
        }
        int[] size=new int[all.size()];
        for (String s : names) {
            String name = s.substring(0, s.indexOf('('));
            size[map.get(name)] = Integer.parseInt(s.substring(s.indexOf('(') + 1, s.indexOf(')')));
        }
        Bing bing=new Bing(all.size(),size);
        for (String synonym : synonyms) {
            String name1=synonym.substring(1,synonym.indexOf(','));
            String name2=synonym.substring(synonym.indexOf(',')+1,synonym.indexOf(')'));
            String n1=n.get(bing.find(map.get(name1)));
            String n2=n.get(bing.find(map.get(name2)));
            if (n1.compareTo(n2)<0){
                bing.union(map.get(n2),map.get(n1));
            }else {
                bing.union(map.get(n1),map.get(n2));
            }
        }
        Set<String> stringSet=new HashSet<>();
        List<String> ans=new ArrayList<>();
        for (String name : all) {
            String fa=n.get(bing.find(map.get(name)));
            if (!stringSet.contains(fa)){
                ans.add(fa+"("+bing.size[bing.find(map.get(name))]+")");
                stringSet.add(fa);
            }
        }
        String[] re=new String[ans.size()];
        for (int i=0;i<ans.size();i++){
            re[i]=ans.get(i);
        }
        return re;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionInterview17_7().trulyMostPopular(new String[]{"a(10)","c(13)"}, new String[]{"(a,b)", "(c,d)", "(b,c)"})));
    }
}
